package org.nowcoder.leetcode.twoPointers;

/**
 * Title  : 82. Remove Duplicates from Sorted List II
 * Source : https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/?envType=study-plan-v2&envId=top-interview-150
 * Author : XrazYang
 * Date   : 2023-07-17
 */

public class LeetCode_82 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode deleteDuplicates(ListNode head) {
        //暴力解法：忽视了条件 "The list is guaranteed to be sorted in ascending order."
        // Map<Integer, Integer> nodeMap = new TreeMap<>();
        // ListNode p = head;
        // while (p != null) {
        //     if (nodeMap.containsKey(p.val)) {
        //         Integer value = nodeMap.get(p.val);
        //         nodeMap.put(p.val, value + 1);
        //     } else {
        //          nodeMap.put(p.val, 1);
        //     }
        //     p = p.next;
        // }
        // head = null;
        // for (Map.Entry<Integer, Integer> entry : nodeMap.entrySet()) {
        //     if (entry.getValue() == 1) {
        //         ListNode node = new ListNode(entry.getKey());
        //         if (head == null) {
        //             head = node;
        //         } else {
        //              p.next = node;
        //         }
        //         p = node;
        //     }
        // }
        // return head;

        //处理特殊情况
        if (head == null || head.next == null) {
            return head;
        }

        //[p,q]区间长度大于1，表示这个区间的元素存在重复，删除
        //初始值： p = head ,q = head.next
        ListNode p = head, q = head.next;
        head = null;
        ListNode node = null;
        while (q != null) {
            if (p.val == q.val) {
                q = q.next;
                if (q == null && node != null) {
                    node.next = null;
                }
            } else {
                if (p.next == q) { //区间长度为1 表示这个元素没有重复元素
                    if (head == null) {
                        head = p;
                    } else {
                        node.next = p;
                    }
                    node = p;
                }
                p = q;
                q = q.next;
                if (q == null) {
                    if (head == null) {
                        head = p;
                    } else {
                        node.next = p;
                    }
                }
            }
        }
        return head;
    }
}
